The present invention relates to a data distribution method or use in a data distrbution apparatus which is capable of equally distributing the data processing loads of a large amount of data or work units over a group of memories and enabling efficient parallel processing of a large amount of data or work units.
FIG. 4 illustrates the coupling units employed in the data distribution apparatus proposed in Japanese Patent Application No. 185561/90. In FIG. 4, reference numeral 1 denotes a coupling unit, numerals 2 and 3 two data input lines of the coupling unit, numerals 4 and 5 two data output lines of the coupling unit, numeral 6 a switch for switching the data connecting patterns in the coupling unit, numeral 7 a group of counters corresponding to each kind of data or work unit, and numeral 8 the control unit which serves to control the group of counters and switch the data connecting patterns in accordance with the contents of the counter group 7. A first pattern in which the input lines 2 and 3 are connected to the output lines 4 and 5, respectively (hereinafter referred to as "parallel pattern"), and a second pattern in which the input lines 2 and 3 are connected to the output lines 5 and 4, respectively (hereinafter referred to as "cross pattern") are shown. FIG. 5 illustrates two data connection patterns that are realized by the switch 6 in the coupling unit 1. In FIG. 5, the upper pattern corresponds to "parallel pattern" and the lower pattern corresponds to "cross pattern". FIG. 6 illustrates the general constitution of the conventional data distribution apparatus. In FIG. 6, reference numeral 9 denotes a data distribution apparatus, numeral 10 a first memory group and numeral 11 a second memory group.
In the system shown in FIG. 6, coupling units 1 are arranged in a matrix comprising 4.times.3 rows. This is because the first memory group 8 comprises 10 memories and it is therefore necessary to provide 4 units (each having two input lines) in each vertical row and log.sub.2 8=3 rows in each horizontal row. Generally, it is necessary, in order to distribute data equally by use of a first group of N memories and a second group of N memories, to form a data distributing apparatus comprising a group of coupling units which are arranged in a matrix of (N/2).times.log.sub.2 N rows. It should be noted that there are various other methods of arranging a network which comprises a plurality of coupling units, and that the technique according to the present invention may be similarly effectively applied to these methods. The details of the coupling unit arrangement shown in FIG. 6 and other coupling unit arrangements are explained in the report of the Electronic Communication Society Proceedings Vol. J86-D, No. 6, p. 1272.
The first memory group is adapted to store at a minimum the data or the work units to be processed. The second memory group is used as a tentative storage area for processing the data or the work units stored in the first memory group. A plurality of coupling units 1 are used for equally distributing in the second memory group 11 the data or work units that are stored in the first memory group 10.
Operation of the data distribution apparatus will now be explained. For the sake of description, it is assumed that the object of distribution is data only, and that data are transferred from the first group 10 of N memories to the second group 11 of N memories after being classified into K different kinds of data. More specifically, each of the data belongs to any of the kinds from 0 to K-1. According to a prior art, if the total Nx number of the data for the 4Xth (X=0, . . . , K-1) kind are transferred from the first group 10 of memories to the second group 11 of memories, Nx/N number of data for each memory are transferred to the second group 11 of memories. Thus each Nx/N number of data are transferred to the second memory group and the data for all kinds of the X-th (X=0. . . , K-1) data are distributed to the second memory whereby data distribution will be completed.
As the data distribution operation is started, data are successively sent from the first group 10 of memories to either of the data input lines 2 or 3 of the coupling units in the first row, which are connected with the respective memories in the first group. Each coupling unit 1 in the first row sets either one of the two connection patterns for the switch 6 shown in FIG. 5, according to the instruction from the control circuit 8, to move the input data in accordance with the switch 6 which has been set and transfer the data to the coupling units in the second row which is connected to the coupling unit 1 concerned, through either of the data output lines 4 or 5, thence repeats this operation. The respective coupling units 1 in the second row and those in the subsequent rows also repeat a similar operation. Data that are output through either of the data output lines 4 or 5 of each coupling unit 1 belonging to the final row are stored separately in the respective corresponding memories in the second memory group 2 while being arranged according to kind.
The control circuit 8 determines the connection patterns for the switch 6 in the following manner. Prior to data distribution, the group 7 of counters for the respective coupling unit 1 are all initialized to zero. The counters in the group 7 are so controlled that when data belonging to X-th (X=0, . . . , K-1) kind are output from the data output line 4, the X-th counter in the counter group 7 is increased by "1". Also, if similar data are output from the data output line 5, the counter group 7 is so controlled by the control circuit 8 that "1" is subtracted from the Xth counter in the counter group 7. More specifically, if the count of the X-th counter in the counter group 7 is positive at a certain point in time, it means that the majority of the data of the X-th kind output from the coupling unit 1 up to that time was delivered through the data output line 4. Similarly, if the count of the counter in the counter group 7 is "0", it means that only half of the number of the data of the X-th kind output from this coupling unit 1 up to that time were delivered through the data output line 4, and the remaining half of the data were delivered through the data output line 5. It is therefore to be noted that as a result, data belonging to the X kind are equally distributed and output as far as this coupling unit 1 is concerned. If the count of the counter in the counter group 7 is negative, it means that the majority of the data was delivered through the data output line 5. In the example shown in FIG. 4, the counts of the counters in the counter group 7 are and "1", "5", "0", and "-2" respectively. This means that "1" indicates that the number of data of the 0-th kind delivered by the data output line 4 is greater than the data delivered by the data output line 5 by one, "5" indicates that the number of data of the first kind delivered by the data output line 4 is greater than the data delivered by the data output line 5 by five, "0" indicates that the number of data of the second kind delivered by the data output line 4 is equal to the data delivered by the data output line 4 and "-2" indicates that the number of data of the third kind delivered by the data output line 5 is greater than the data delivered by the data output line 4 by two.
Thus, it is possible by means of the counter group 7 to control the condition of local distribution of the data delivered through the two output lines 4 and 5 of the coupling unit 1 concerned for each kind of data. It is necessary, in order to realize equal distribution of data for each kind, to output the same number of data for each kind to each of the output lines in the coupling unit, which is equivalent to the fact that the counts of all the counters in the group 7 are all "0" at the time of completion of data distribution.
The control circuit 8 of the respective coupling unit seeks the difference in the counter values corresponding to the kind of incoming data each time data are transmitted to the data input line 2 or the data input line 3. If the counter value is positive or zero, the control unit 8 connects the data input lines 2 or 3 to the data output lines 5 or 4, respectively. If said value is negative, the control circuit connects the data input lines 2 and 3 to the data output lines 4 and 5, respectively, thereby determining the connection patterns for the switch 6. The data which have been sent to the data input lines 2 or 3 are delivered to the data output lines 4 and 5 in accordance with the thus determined connection patterns for the switch 6, and further delivered to the group of coupling units connected to these data output lines.
For example, it is assumed that data which belong to the 0-th kind are input through the data input line 2 and data which belong to the first kind are inputted through the data input line 3, and the counts of the counters corresponding to these kinds are "1" and "5" respectively. This means that the number of data of the 0-th kind input to the coupling unit and output by the data output line 4 up to that time is greater than that of the data output by the data output line 5 by one, and similarly, the number of data of the first kind output by the data output line 4 is greater than the data output by the data output line 5 by five. In this case, since data distribution is deviated to data of the first kind rather than data of 0-th kind, it is advantageous if the data input line 2 is connected to the data output line 4 and the data input line 3 is connected to the data output line 5, so as to reduce such deviation of distribution of data of the first kind. According to the above-described method, the difference between the counts of the two counters is negative since 1-5=-4, and the connection pattern for this value is selected for the switch 6.
According to the data distribution apparatus of a prior art which is constituted as above described, the number of data or work units may be equally distributed. However, since the processing load of the data or the work units varies depending on their contents, the processing load will not be equal if, in actuality, the data processing is executed by the second group 11 of memories. For example, even if data are distributed equally from the first group 10 of memories to the second group 11 of memories, when the distributed data or work units are processed by the second group 11 of memories, the processing time is determined by completion of processing by the memory in the second memory group 11 which is the most heavily loaded and takes the longest processing time, resulting in extended processing time. It was also a problem that many of the memories in the second memory group caused the working efficiency to be lowered. Under these circumstances, if a large number of data or work units are to be processed, the processing efficiency is lowered.